// 1. 简单-509-斐波拉契
// 2. 118-杨辉三角
// 3. 简单-70-爬楼梯
// 4. 简答-746-使用最小花费爬楼梯
// 5. 198-打家劫舍
// 6. 322-零钱兑换
// 7.279-完全平方数
// 8.139-单词拆分
// 9.416-分割等和子集
// 10. 简单-62-不同路径
// 11. 简单-63-不同路径2
// 12.编辑距离-72-编辑距离

// 13.最小路径和

// 14. 子序列(不连续)-300-最长上升子序列
// 15. 子序列(不连续)-1143-最长公共子序列
// 16. 子序列(连续)-718-最长重复子数组（最长公共子串）







////////////////////
// 17. 回文-516-最长回文序列
// 10. 回文-647-回文串
// 12. 简答-343-整数拆分
// 12. 编辑距离-115-不同子序列
// 13. 编辑距离-583-两个字符串的删除操作





// 1.斐波拉契数列
// 题意：给定n，计算fn
// 思路：正循环，递推公式决定了i从2起始；递推公式 dp[i] = dp[i - 1] + dp[i - 2]，返回dp[n]
// 注意：初始化[0,1]
var fabric = (n) => {
  let dp = [0, 1]
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2]
  }
  return dp[n];
}
console.log(fabric(2))

// 2.杨辉三角
// [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
var generate = function(numRows) {
  let res = []
  for(let i = 0; i< numRows; i++){
      let row = new Array(i+1).fill(1)
      for(let j = 1; j < row.length -1; j++){ // -1 +1 两端都是1 且容易越界
          row[j] = res[i -1][j-1]+res[i-1][j]
      }
      res.push(row)
  }
  return res

};

// 3.爬楼梯
// 题解：有多少种可能， 每次一步或则两部
// 思路：dp 第i个阶梯有多少种方法爬到楼顶；正循环，递推公式决定了i从2起始；题解公式 dp[i] = dp[i - 1] + dp[i - 2]，返回dp[n-1]
// 注意：初始化[1,2]
var clampStairs = (n) => {
  let dp = [1, 2]
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2]
  }
  return dp[n - 1]
}
console.log(clampStairs(3))

// 4.使用最小花费爬楼梯
// 题解：每一层需要收钱，每次一步或则两部
// 思路：dp 到达第i个阶梯的最小花费；正循环递推公式决定了i从2起始；题解公式 dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i-2]+cost[i-2])；返回dp[n]
// 注意：初始化[0,0]
var minCoastClampStairs = (cost) => {
  let dp = [0, 0]
  for (let i = 2; i <= cost.length; i++) {
    dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i-2]+cost[i-2])
  }
  return dp[cost.length]
}
console.log(minCoastClampStairs([3, 5, 6]))

// 5.打家劫舍
var rob = function(nums) {
    let dp = new Array(nums.length);
    dp[0] = 0; // 补一位
    dp[1] = nums[0]
    for(let i = 2; i<= nums.length; i++){
        // 不能相邻所以2 要加自身, 由于补了一位，所以当前值为nums[i-1]
        dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i-1]) 
    }

    return dp[nums.length]
};

// 6.零钱兑换
// 先物品，再背包， 是求组合数 （要求顺序）
// 现背包，再物品，是求排列数（不要求顺序） - 本题求最小可能两种方式都可以
var coinChange = function(coins, amount) {
  // 目标值是背包容量，钱是物品，使用最少的物品装满背包
  let dp = new Array(amount + 1).fill(Infinity);
  dp[0] = [0];
  for(let i = 1; i<= amount; i++){// 先背包
      for(let j = 0; j < coins.length; j++){
          if(i >= coins[j] ){
              dp[i] = Math.min(dp[i], dp[i- coins[j]] + 1)
          }
      }
  }

  return dp[amount] === Infinity ? -1: dp[amount];
};


// 7.完全平方数
// n 是背包容量，1-> i-j*j 就是可能
var numSquares = function(n) {
  let dp = new Array(n+1).fill(0)
  dp[0] = 0;

  for(let i = 1; i<= n; i++){
      dp[i] = i; // 最歪的情况是每次加1
      for(let j = 1; j*j <= i; j++){
          dp[i] = Math.min(dp[i], dp[i - j*j] + 1)
      }
  }

  return dp[n]
};

// 8.单词拆分
var wordBreak = function(s, wordDict) {
  let wordSet = new Set(wordDict)
  // dp 含义 长度为i的s(0, i-1)是否由单词表组层
  const dp = new Array(s.length + 1).fill(false)
  dp[0] = true
  // 求排列数 先背包再物品
  for(let i =1; i<= s.length; i++){
      for(let j = i-1; j >=0; j--){
          const suffix = s.slice(j, i); // 后缀部分 s[j, i-1]
          if(wordSet.has(suffix) && dp[j]){ // 后缀是单词，左侧[0, j-1]为真
              dp[i] = true; // 长度为i 可以由单词构成
              break; // 不需要继续划分了
          } 
      }
  }

  return dp[s.length]
};




// 9.分割等和子集
var canPartition = function(nums) {
  // 背包问题 容量sum/2 
  if(nums.length < 2) return false;
  let sum = 0;
  for(const num of nums){
      sum += num
  }
  
  if(sum % 2 === 1) return false // 小数无法平均分
  const target = Math.floor(sum/2)

  // dp[i][j], 表示从0-i选若干元素能否使和为j，初始都是false
  const dp = Array.from(Array(nums.length), () => Array(target + 1).fill(false));
  for(let i =0; i< nums.length; i++){
      dp[i][0] = true // 0-0 表示没有元素可选取
  }
  // 
  for(let i = 1; i< nums.length; i++){
      for(let j =1; j <= target; j++){
          if(j>= nums[i]){
              dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]] // 不选上一个，选了 那要看 和-当前元素 的和是否存在
          } else {
              dp[i][j] = dp[i-1][j] // 上一个 不可能 和小于当前值
          }
      }
  }
  return dp[nums.length - 1][target]

  // // 转换为能否装满 能否到达dp[target] = target dp[j] 含义：容量为j，能否有一种组合使和为j
  // const dp = new Array(target + 1).fill(false)
  // dp[0] = true;
  // for(const num of nums){
  //      for(let j = target; j>= num; j--){  
  //     // 为什么是倒叙「从后向前」 ; 因为如果我们从小到大更新dp值，那么在计算 dp[j]值的时候，
  //     // dp[j−nums[i]] 已/// 经是被更新过的状态，不再是上一行的 dp 值。
  //         dp[j] = dp[j] || dp[j - num]
  //     }
  // }
  // return dp[target]

};

// 10. 不同路径
// 题解：m, n的方阵，只能从下和右走
// 思路：dp 二维数组，dp[i][j]代表到达这个位置的几种可能，初始化横向纵向都是1；循环正向循环，递推公式dp[i][j] = dp[i - 1][j] + dp[i][j - 1]；返回 dp[m - 1][n - 1]
// 注意：要注意初始化
var uniquePath = (m, n) => {
  const dp = new Array(m).fill(0).map(res => new Array(n).fill(0));
  // 初始化 行/列
  for (let i = 0; i < m; i++) {
    dp[i][0] = 1
  }
  for (let i = 0; i < n; i++) {
    dp[0][i] = 1
  }
  // 数据定义, 遍历顺序, 初始位置都要从1 起
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    }
  }
  return dp[m - 1][n - 1]
}
console.log(uniquePath(3, 7))

// 11. 不同路径2
// 题解：相对于不同有障碍 
// 思路：dp 二维数组，dp[i][j]代表到达这个位置的几种可能，初始化横向纵向都是1；循环正向循环，递推公式dp[i][j] = dp[i - 1][j] + dp[i][j - 1]；返回 dp[m - 1][n - 1]
// 注意：要注意处理障碍，有障碍的位置是计算结果dp[i][j]为0
var uniquePath2 = (obstacleGrid) => {
  const m = obstacleGrid.length;
  const n = obstacleGrid[0].length;
  let dp = new Array(m).fill(0).map(res => new Array(n).fill(0));
  for (let i = 0; i < m && obstacleGrid[i][0] === 0; i++) {
    dp[i][0] = 1
  }
  for (let i = 0; i < n && obstacleGrid[0][i] === 0; i++) {
    dp[0][i] = 1
  }

  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[i][j] = obstacleGrid[i][j] === 1 ? 0 : dp[i - 1][j] + dp[i][j - 1]

    }
  }
  return dp[m - 1][n - 1]
}
console.log(uniquePath2([[0, 0, 0], [0, 1, 0], [0, 0, 0]]))

// 12.编辑距离1
var minDistance = function(word1, word2) {
  // dp 表示word1的前i个字符和word2前j个字符的边界距离
  let dp = Array.from(Array(word1.length+1), ()=> Array(word2.length+1).fill(0))

  // 初始化dp
  for(let i = 1; i<= word1.length; i++){
      dp[i][0] = i
  }
  for(let i = 1; i<= word2.length; i++){
      dp[0][i] = i
  }

  for(let i =1; i<= word1.length; i++){
      for(let j =1; j<=word2.length; j++ ){
          if(word1[i-1] === word2[j-1]){
              dp[i][j] = dp[i-1][j-1]// 最后一个字符相同，不用操作
          } else {
              // dp[i-1][j] + 1：对应 word1删除最后一个字符
              // dp[i][j-1] + 1：对应新增 word1增加一个字符
              // dp[i-1][j-1] + 1：对应 word1替换最后一个字符 
              dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
          }
      }
  }

  return dp[word1.length][word2.length]
};vs

// 13.最小路径和
// 依旧是下，右, 加了一个最小值
var minPathSum = function(grid) {
  let m = grid.length;
  let n = grid[0].length;
  // dp代表的是每个位置的最小路径和
  for(let i =1; i < m; i++){
      grid[i][0] = grid[i-1][0] + grid[i][0]
  }

  for(let i= 1; i< n; i++){
      grid[0][i] = grid[0][i-1] + grid[0][i]
  }

  for(let i =1; i< m; i++){
      for(let j =1; j< n; j++){
          grid[i][j] = Math.min(grid[i-1][j], grid[i][j-1]) + grid[i][j]
      }
  }

  return grid[m-1][n-1]
};


// 14.最长上升子序列（在原有的, 不需要连续） ----- 最长连续序列区别（自己组合，连续+1）
// 题解：寻找最长的上升序列，
// 思路：dp 代表：从0到下标为i的序列的最长子序列长度，两层循环判断ij位置是否递增，取最大值，递推公式：dp[i] = Math.max(dp[i], dp[j] + 1) // Math.max(...dp)
// 注意：i 与i前面的元素比较： 当前位置的最长, 是自己位置前所有结果的最大值
var lengthOfLIS = (nums) => {
  const dp = new Array(nums.length).fill(1); // dp 代表：从0到下标为i的序列的最长子序列长度
  for (let i = 0; i < nums.length; i++) {
    // i 与i前面的元素比较： 当前位置的最长, 是自己位置前所有结果的最大值
    for (let j = 0; j < i; j++) {
      if (nums[i] > nums[j]) { // 如果是递增，则结果+1
        dp[i] = Math.max(dp[i], dp[j] + 1) // 尾比 3 小的子序列，然后把 3 接到最后，就可以形成一个新的递增子序列，而且这个新的子序列长度加一
      }
    }
  }
  return Math.max(...dp)
}
console.log(lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18])) // [2,3,7,101]



// 15.最长公共子序列(不连续)
// 题解：两个字符的公共子序列
// 思路：dp[i][j]：表格位置 i,j 上的数字含义是， 字符串 a' 和 b' 的、以它们尾巴字符结尾的、最长公共子序列的长度 。
//      假设，已经知道 i-1, j-1 处的dp数值，考虑位置 i, j 的数值：
//      如果 a[i-1] == b[j-1]， 则填写 dp[i][j] = dp[i-1][j-1] + 1 // 如果位置相等，则最长公共子序列得到扩展，因此，数值加一。
//      否则，填写 dp[i][j] = max(dp[i-1][j], dp[i][j-1]) // 如果位置不相等则公共子序列是i和j前一个位置的最大值
// 注意：起始为1
var commonSub = (text1, text2) => {
  // 转换二维数组
  // let dp = Array.from(Array(text1.length + 1), () => Array(text2.length + 1).fill(0)) // + 1是关键
  const m = text1.length;
  const n = text2.length;
  const dp = new Array(m + 1);
  for (let i = 0; i <= m; i++) { // 初始化整个dp矩阵，每个值为0
    dp[i] = new Array(n + 1).fill(0);
  }
  // console.log(dp) // dp含义：dp[i][j]：长度为[0, i - 1]的字符串text1与 长度为[0, j - 1]的字符串text2的 最长公共子序列为dp[i][j]
  for (let i = 1; i <= text1.length; i++) { // 长度= 也是一个重点
    for (let j = 1; j <= text2.length; j++) {
      // 计算dp[i][j]: 条件判断
      // 如果字符 a[i] 和 b[j] 相同，则最长公共子序列得到扩展，数值加一。
      // 否则，采用左边的和上面的方格中的数值的最大值【见图】：https://writings.sh/post/algorithm-longest-common-substring-and-longest-common-subsequence
      if (text1[i - 1] === text2[j - 1]) { // 因为索引从1开始的 所以取值i-1
        dp[i][j] = dp[i - 1][j - 1] + 1
      } else {
        dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j])
      }
    }
  }
  return dp[text1.length][text2.length]
}
console.log(commonSub(text1 = "abcde", text2 = 'ace'))


// 16. 最长公共子串（连续）最长重复子数组
// 思路：dp[i][j]：表格位置 i,j 上的数字含义是， 字符串 a' 和 b' 的、以它们尾巴字符结尾的、最长公共子串的长度 。
//      假设，已经知道 i-1, j-1 处的dp数值，考虑位置 i, j 的数值：
//      如果 a[i-1] == b[j-1]， 则填写 dp[i][j] = dp[i-1][j-1] + 1 // 如果位置相等，则最长公共子串得到扩展，因此，数值加一。
//      否则，填写 dp[i][j] = 0 // 如果位置不相等则没有公共子串，由于已经初始化0 可直接获取结果
// 注意：起始为1
var findLength = (text1, text2) => {
  const m = text1.length;
  const n = text2.length;
  const dp = new Array(m + 1);
  for (let i = 0; i <= m; i++) { // 初始化整个dp矩阵，每个值为0
    dp[i] = new Array(n + 1).fill(0);
  }
  let res = 0;
  for (let i = 1; i <= text1.length; i++) {
    for (let j = 1; j <= text2.length; j++) {
      if (text1[i - 1] === text2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1
      }
      res = Math.max(res, dp[i][j]) // dp[i][j] = 0 已经不连续了
    }
  }
  return res
}
console.log(findLength(text1 = "abcde", text2 = 'ace'))


// 9. 回文串，所有可能
// 题解：给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
// 思路：
// 注意：


// 17. 最长回文序列 （不连续）与最长回文长度（map）
// 题解：字符串反转后和原字符串的最长回文 就是  最长回文子序列 。 
// 思路：dp代表的时候ij位置，最长的回文,外层倒序，内层正序
//      如果 s[i] === s[j]， 则填写 dp[i][j] = dp[i+1][j-1] + 2 // 如果位置相等，回文成立数量+2
//      否则， dp[i][j] = Math.max(dp[i][j - 1], dp[i + 1][j]) // 前一个位置的回文最大值
// 注意：结果dp[0][strLen - 1]，循环一个正序一个倒序
var longestpalindromeSub = (s) => {
  let strLen = s.length;
  let dp = Array.from(Array(strLen), () => Array(strLen).fill(0)); // 串 i..j 内的最长回文序列长度。
  for (let i = 0; i < strLen; i++) {
    dp[i][i] = 1
  }

  for (let i = strLen - 1; i >= 0; i--) { // 倒叙
    for (let j = i + 1; j < strLen; j++) {
      if (s[i] === s[j]) {
        dp[i][j] = dp[i + 1][j - 1] + 2
      } else {
        dp[i][j] = Math.max(dp[i][j - 1], dp[i + 1][j])
      }
    }
  }
  return dp[0][strLen - 1]
}
console.log(longestpalindromeSub("bbbab"))




// 编辑距离2
// 编辑距离3






///////// 子序列/子串问题
// 1. 最长公共子序列 /最长公共子串（dp）
// 2. 最长上升子序列（dp）
// 3. 最大连续子序列和 （greedy - 判断递增循环）
// 5. 最长无重复子串（map）
// 6. 最长连续上升序列（map）
// 7. 和为k的子串（连续）（map-前缀和） 和为k的子序列